% author: Starrysky
% last update date: 2022-10-09
% description: 以 UTF-8 编码保存, 使用 XeLaTeX 编译

% 使用CTex宏集以支持中文
\documentclass[UTF8]{ctexart}
% 从此处到正文开始前是导言区, 进行文档全局设置
% 设置页面大小和页边距
\usepackage[a4paper, margin=1in, bottom=0.5in]{geometry}
% 支持数学公式
\usepackage{amsmath}
% 支持超链接
\usepackage{hyperref}
% 支持图片
\usepackage{graphicx}
% 设置图片文件目录
\graphicspath{{./resources}}
% 支持伪代码
\usepackage{algorithm}
\usepackage{algorithmic}

% 编写C++程序
\usepackage{listings}
\usepackage{xcolor}
\definecolor{mygreen}{RGB}{0,0.6,0}
\definecolor{mygray}{RGB}{0.5,0.5,0.5}
\definecolor{mymauve}{RGB}{0.58,0,0.82}

\lstset{ %
	backgroundcolor=\color{white},   % choose the background color
	basicstyle=\footnotesize\ttfamily,        % size of fonts used for the code
	columns=fullflexible,
	breaklines=true,                 % automatic line breaking only at whitespace
	captionpos=b,                    % sets the caption-position to bottom
	tabsize=4,
	commentstyle=\color{mygreen},    % comment style
	escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
	keywordstyle=\color{blue},       % keyword style
	stringstyle=\color{mymauve}\ttfamily,     % string literal style
	frame=single,
	rulesepcolor=\color{red!20!green!20!blue!20},
	% identifierstyle=\color{red},
	language=c++,
}
% 替换为Input和Output
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\title{贪心算法\;书面作业}
\author{方仕元\;202228013229063}
\date{\today}
% 正文部分
\begin{document}

% 显示导言区设置的title、author、date等信息
\maketitle
% 显示目录，目录要编译两次
\tableofcontents
% 分页
\newpage

% 多级section、paragraph的排版
\section{Solution for \emph{Question 1}}

\subsection{算法描述}
每次修整$S$中最长的坑；若最大的坑超出剩余预算，则直接把全部剩余预算用于修整。直至预算耗尽，返回字符串中\emph{字符.}的个数。伪代码如下: 

\begin{lstlisting}
int maxNormalRoad(const string &raw, const long M){
	string visited=raw; // copy
	while(M>0){
		left_edge, right_edge=visited中最长连续'.'子串的起始下标和中止下标
		const long size=right_edge-left_edge+1;
		/* pit数量超过预算*/
		if(M<size+1){
			const long tmp=M-1;
			visited[left_edge: left_edge+tmp]='.'; // 将路修整
			M=0;
		} else {
			M-=size+1;
			visited[left_edge: right_edge+1]='.';
		}
	}
	return 字符串visited中的'.'的数量
}
\end{lstlisting}


\subsection{正确性证明}
初始字符串$S$中，设normal road总长度为$C$。设预算下修整的pit总数为$N$，则最终normal road长度为$N+C$。由于$C$为一常量，所以只需求$N$的最大值即可。

设待修整的pit段数为$n$，每次修整需额外支付1，则$N=M-n$，所以只需求$n$的最小值即可。为了使$n$最小，只需每次支付的数额足够大，即每次修整最长的pit。

\section{Solution for \emph{Question 3}}
\subsection{算法描述}
解：每次选开始最早的课。若没有教室或者所有教室已占用，则开辟一间新教室。最后统计教室总数。

伪代码如下：
\begin{lstlisting}
int minNumRooms(const std::vector<std::pair<int,int>> &raw){
	int totalCount=0;
	std::sort(raw, 根据开始时间，从早到晚);
	
	std::priority_queue<int> room; // 保存教室的占用结束时间, 最早结束的先出队
	for(interval in raw){
		if(room.empty() or room.first结束时间 > interval.first){
			// 安排新房间
			room.push(interval.second);
			totalCount++;
		} else {
			// 更新教室的结束时间
			room.pop();
			room.push(interval.second);
		}
	}
	
	return totalCount;
}
\end{lstlisting}
\subsection{正确性证明}
设所有课程已根据开始时间从早到晚排序。
安排新课时，如果当前时刻不存在空闲教室，那么显然只能另外开辟一间新教室供使用。

如果存在空闲教室，下面用反证法证明：将旧教室安排给新课是最优解，理由如下。

如果另外创建一间新教室，且能获得最优解。设安排新课之前的可用旧教室为$r_1$，新课占用
的新教室为$r_2$，新课的开始时间为$t$。那么，将教室$r_2$中的所有课程与教室$r_1$中时刻$t$之后的课程进行对调，不会有时间冲突，因此是一个新的排课方案。这种排课方案的课程数量并没有增加，因此也是一个最优解。

由此可知，将旧教室$r_1$安排给新课可以获得最优解。

综上所述，本节给出的算法是正确的。



\section{Solution for \emph{Question 4}}
\subsection{算法描述}
解：原问题等价于，从原始数中从左到右挑选若干个数字并组成新数，使这个数字最大。
设一共要挑选$n$个数字，原始数从左到右下标从0开始。
当要挑选第1个数字时，可挑选的下标从0开始，并末端要保留$n-1$个数字供后续选择；从中挑选最大的数字，设其下标为$p_1$
当要挑选第2个数字时，可挑选的下标从$p_1+1$开始，并且末端要保留$n-2$个数字供后续选择，从中挑选最大的数字。
以此类推，直到挑选完成$n$个数字


伪代码如下:
\begin{lstlisting}
int maxSubNumber(const int raw, const int n){
	const std::vector<int> carrier=raw的从左到右各位数字;
	std::vector<int> result;
	for(int i=0; result.size()<n;){
		const int k=result.size();
		const int pos=下标从i开始，排除末端(n-k-1)个数的，carrier中的最大数字，的下标
		result.push_back(carrier[pos]);
		i=pos+1;
	}
	return 顺序连接carrier中的各个数字
}
\end{lstlisting}
\subsection{正确性证明}
用数学归纳法进行证明。
当挑选第一个数字时，保留了末端$n-1$个数字，可保证最终一定能挑出$n$个数字。
从剩下的数挑选最大的，可保证最终首位数最大。

设已经挑选了$k$个数字。当挑选第$k+1$个数字时，保留了末端$n-k-1$个数字。从中挑选最大数字，可保证最大。

\section{Solution for \emph{Question 5}}
\subsection{算法描述}
当选择下一跳时，应选择辐射范围最远的点。这里简单解释一下"辐射范围"的含义。
设数组中某个数的下标为$i$，其数值为$num_i$，则从它出发，最远可直达的下标为$i+num_i$，可以形象的解释为"辐射范围"。

伪代码如下:
\begin{lstlisting}
// 从下标pos开始，选择下一跳的下标
int selectFar(const std::vector<int> &raw, const int pos){
	const int left=pos;
	const int len=raw[pos];
	const int right=std::min(left+len,raw.size()-1);
	int maxpos=left+1;
	for(int i=left+1;i<=right;i++){
		if(maxpos+raw[maxpos]<i+raw[i]){
			maxpos=i;
		}
	}
	if maxpos
	return maxpos;
}

bool canReach(const std::vector<int> &raw){
	int i=0;
	while(i<raw.size()-1){
		i=selectFar(raw,i);
	}
	return i>=raw.size();
}

\end{lstlisting}

\subsection{正确性证明}
不妨先设能到达终点，下面用反证法证明。

设当前位于下标$a$，下标$b$是$a$可到达范围内的、辐射范围最远的点。假设从$a$出发有一条路线$a,c,d,e,f ...$，可以到达终点，但是这条路线上没有点$b$。
+ 1. 情况1：$b$在$a$和$c$之间，由于$b$的辐射范围不低于$c$，所以$b$也能直达$d$，因此路线$a,b,d,e,f...$也能到达终点。
+ 2. 情况2: $b$在$c$的右侧，在$d$的左侧。同理，$b$也能直达$d$，到终点的路线同样存在。
+ 3. 情况3: $b$在$d$的右侧，间接说明$a$可以直达$d$。由于$b$的辐射范围不低$d$，所以$b$能直达$e$。
综上所述，如果存在到终点的路线，那么一定有条路线包含点$b$。

假设不能到达终点，也可以通过上面的方法推理，不赘述。

%\section{公式}
%首先，$a+b=c$是一个行内公式。下面看一个行间公式:
%\[
%    a^2+b^2=c^2
%\]
%
%
%对公式进行编号
%\begin{equation}
%    a^2+b^2=c^2
%\end{equation}
%
%
%更复杂的公式，可以辅以这个工具：\href{https://www.latexlive.com/}{https://www.latexlive.com/}
%
%
%\section{图片}
%如图\ref{fig:1}所示.
%\begin{figure}[H]
%    \centering
%    \includegraphics[width = .8\textwidth]{./一拳把地球打爆.jpg}
%    \caption{人哪有不疯的 硬撑罢了}
%    \label{fig:1}
%\end{figure}
%
%\section{表格}
%% l、c、r控制对齐方式
%\begin{tabular}{|l|c|r|}
%
%    \hline
%    操作系统       & 发行版      & 编辑器       \\
%    \hline
%    Windows    & MikTeX   & TexMakerX \\
%    \hline
%    Unix/Linux & teTeX    & Kile      \\
%    \hline
%    Mac OS     & MacTeX   & TeXShop   \\
%    \hline
%    通用         & TeX Live & TeXworks  \\
%    \hline
%\end{tabular}
%
%\section{伪代码}
%\begin{algorithm}[H]    
%    \caption{find $n^{th}$ smallest  value from 2n values in two separate databases}
%    \label{algo:1}
%    \textbf{function}  \textbf{FindMidianValue}($DB_a,DB_b,k,head_a,head_b$) 
%    \begin{algorithmic}[1]
%        \IF{$k == 1$}
%            \RETURN $min(query(DB_a, head_a), query(DB_b, head_b))$
%        \ENDIF
%        \STATE $k_a \gets \lfloor \frac{k}{2} \rfloor $
%        \STATE $k_b \gets k - a $
%        \STATE $v_a\gets query(DB_a, head_a+k_a-1)$
%        \STATE $v_b\gets query(DB_b, head_b+k_b-1)$
%        \IF{$v_a<v_b$}
%            \RETURN \textbf{FindMidianValue}($DB_a,DB_b,k-k_a,head_a+k_a,head_b$)
%        \ELSE
%            \RETURN \textbf{FindMidianValue}($DB_a,DB_b,k-k_b,head_a,head_b+k_b$)
%        \ENDIF
%    \end{algorithmic}
%\end{algorithm}
\end{document}